//102
function levelOrder(root) {
  if (root === null) return [];
  const result = [];
  let currentLevel = [];
  let nextLevel = [];
  result.push([root.val]);
  currentLevel.push(root.left, root.right);
  if (currentLevel.every((item) => item === null)) return result;
  while (true) {
    const subResult = [];
    for (let i = 0; i < currentLevel.length; i++) {
      if (currentLevel[i] !== null) {
        subResult.push(currentLevel[i].val);
        nextLevel.push(currentLevel[i].left);
        nextLevel.push(currentLevel[i].right);
      } else {
        subResult.push(null);
        nextLevel.push(null, null);
      }
    }
    result.push(subResult);
    if (nextLevel.every((item) => item === null)) return result;
    currentLevel = nextLevel;
    nextLevel = [];
  }
}
//双缓冲
//好像差球不多
//队列
var levelOrder = function (root) {
  const ret = [];
  if (!root) {
    return ret;
  }

  const q = [];
  q.push(root);
  while (q.length !== 0) {
    const currentLevelSize = q.length;
    ret.push([]);
    for (let i = 1; i <= currentLevelSize; ++i) {
      const node = q.shift();
      ret[ret.length - 1].push(node.val);
      if (node.left) q.push(node.left);
      if (node.right) q.push(node.right);
    }
  }

  return ret;
};
